//方法一：递归   ==>TML
class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount == 0)
        return 0;
        if(amount < 0)
        return -1;

        int res = Integer.MAX_VALUE;
        for(int coin : coins)
        {
            int subProblem = coinChange(coins, amount - coin);
            if(subProblem == -1)
            continue;
            res = Math.min(res, subProblem+1);
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}
/*
总结一些递归了动态规划的区别
    无论是带memo的递归还是普通递归都是自顶向下的寻求答案
    而动态规划则要符合最优子问题
    解释一下最优子问题：是说可以通过子问题的最优解推导出总问题的最优解。
    所有最优子问题就是从下向上一点点的计算答案
*/

//方法二：尾递归

//
class Solution {
    int[] memo;
    public int coinChange(int[] coins, int amount) {
        if(amount == 0)
        return 0;
        memo = new int[amount+1];
        Arrays.fill(memo,Integer.MAX_VALUE);
        return dp(coins,amount);
    }
    public int dp(int[] coins, int amount){
        if(amount == 0)
        return 0;
        if(amount < 0)
        return -1;
        if(memo[amount] != Integer.MAX_VALUE)
        return memo[amount];
        int res = Integer.MAX_VALUE;
        for(int coin : coins){
            int subProblem = dp(coins,amount-coin);
            if(subProblem == -1)
            continue;
            res = Math.min(res,subProblem+1);
        }
        memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res; 
        return memo[amount];
    }
}

//题解
int[] memo;

int coinChange(int[] coins, int amount) {
    memo = new int[amount + 1];
    // dp 数组全都初始化为特殊值
    Arrays.fill(memo, -666);

    return dp(coins, amount);
}

int dp(int[] coins, int amount) {
    if (amount == 0) return 0;
    if (amount < 0) return -1;
    // 查备忘录，防止重复计算
    if (memo[amount] != -666)
        return memo[amount];

    int res = Integer.MAX_VALUE;
    for (int coin : coins) {
        // 计算子问题的结果
        int subProblem = dp(coins, amount - coin);
        // 子问题无解则跳过
        if (subProblem == -1) continue;
        // 在子问题中选择最优解，然后加一
        res = Math.min(res, subProblem + 1);
    }
    // 把计算结果存入备忘录
    memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
    return memo[amount];
}

//本来还有点不理解为啥subProblem要加一
//为啥要在执行递归的函数里面进行 n == 0 和 n < 0 进行判断
//首先是因为sub是子问题，也即是解决 amount - coin 金额需要的钱数，“原问题”和子问题差距就是一枚coin
//第二个问题，因为是递归的出口

//方法三：动态规划
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);//Integer.MAX_VALUE会出错

        dp[0] = 0;
        for(int i=0; i<dp.length; ++i)
        {
            for(int coin : coins){
                if(i-coin < 0)
                continue;
                dp[i] = Math.min(dp[i], dp[i-coin]+1);
            } 
        }
        return (dp[amount] == Integer.MAX_VALUE) ? -1 : dp[amount];
    }
}

//题解
int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    // 数组大小为 amount + 1，初始值也为 amount + 1
    Arrays.fill(dp, amount + 1);

    // base case
    dp[0] = 0;
    // 外层 for 循环在遍历所有状态的所有取值
    for (int i = 0; i < dp.length; i++) {
        // 内层 for 循环在求所有选择的最小值
        for (int coin : coins) {
            // 子问题无解，跳过
            if (i - coin < 0) {
                continue;
            }
            dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
        }
    }
    return (dp[amount] == amount + 1) ? -1 : dp[amount];
}
//解释一下为什么会出错，结果显示是 -2^31
// 明显就是 Integer.MAX_VALUE + 1; 的结果
